In the past, processes to be run on multiprocessing systems, i.e., computer processing systems that include a plurality of central processing units (CPUs), have been scheduled on a common run queue. Every CPU in the multiprocessing system has equal access time to the run queue. When a CPU context change is required due, for example, to the time quantum of the current process expiring, the process being blocked by an I/O request, the CPU selects the process at the head of the run queue, placing the previously running process at the tail of the queue. This scheduling method works well for balancing the workload of a multiprocessor system wherein the majority of the system memory is global, equally available to all CPUs.
Recently, symmetric multiprocessing systems that include a substantial amount of coupled memory have been proposed. In a coupled memory multi-processing system, a memory module is associated, i.e., coupled, to each CPU. The CPU and the memory modules are interconnected via a global interconnect bus that is also connected to a larger global memory. Because all of the CPUs, all of the coupled memories and the global memory are interconnected via the global interconnect bus, all of system memory is available to all of the CPUs.
In addition to the global interconnect bus, the CPUs are coupled to their associated coupled memory via a private bus. As a result, any reference made by a CPU to its associated coupled memory does not have to use the global interconnect bus, except to the extent necessary to maintain memory coherency. Each memory reference that occurs as processes are being run on each CPU is checked to see if it maps to the coupled memory region associated with the CPU. If it does, the private bus is used. Otherwise, the global interconnect bus is used to access the required data from the global memory, or from the coupled memory associated with another CPU. Global interconnect bus bandwidth is saved when the CPU uses its coupled memory because the global interconnect bus is not used.
Because the random movement of processes from one CPU to another does not make the best use of a coupled memory system, a common run queue of the type used with previously developed symmetric multiprocessing systems is undesirable. More specifically, if processes are allowed to move freely from one CPU to another, the cost in interconnect bandwidth is great because all of the data and instructions located in the coupled memory must be moved as part of the process movement; or, the global interconnect bus must be used to access data and instructions in a coupled memory associated with a CPU other than the one running the process.
The present invention is directed to overcoming the foregoing and other problems by providing a method of scheduling processes on the CPUs of symmetric
maintain process-to-CPU affinity without multiprocessing systems that introducing excessive idle time.